iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 24
1
Software Development

LeetCode30系列 第 24

[LeetCode30] Day24 - 458. Poor Pigs

  • 分享至 

  • xImage
  •  

題目

  • Example:

    1. 有1000個水桶,只有一個是有毒的,其餘的則裝滿水,你沒辦法分辨哪個是毒水。
    2. 如果小豬喝了毒藥,它將在15分鐘內死亡。
    3. 您需要在60分鐘內弄清楚哪個桶有毒的
      最少需要幾隻小豬才能做到?
  • 請解決General case:

    1. buckets個水桶,只有一個是有毒的,其餘的則是一般的水,你沒辦法分辨哪個是毒水。
    2. 如果小豬喝了毒藥,它將在minutesToDie分鐘後死亡。
    3. 您需要在minutesToTest分鐘內弄清楚哪個桶有毒的
      最少需要幾隻小豬才能做到?
  • Notes

    • 小豬能同時喝很多桶水,且喝的時間不考慮
    • 喝完後的m分鐘內,不能再進食。
    • 任何桶的水無限供應,小豬也無限供應。

分析

  1. 首先,我們有
    • 桶數 buckets
    • 觀察時間 minutesToDie
    • 測試時間 minutesToTest
    • 求 小豬數 p
  2. 測試次數T = 測試時間/觀察時間 (minutesToTest/minutesToDie)
    • 以上面的例子 T = 60/15 = 4
    • T很重要,代表每隻小豬最大能測試的次數!
    • minutesToDieminutesToTest算完就沒用了
  3. 再來我們觀察一下小的case:
    • buckets=2, T=1
    • 我們讓1隻小豬去試其中一桶
      • 小豬不幸死亡: 找到
      • 小豬不幸(?)活著: 代表沒被試的那桶有毒
    • Ans: p=1
      會發現測試次數只有1,但你其實隱式地測了1次,1+1=2
  4. 讓我們換個角度: 有Tp,能測的最大桶數buckets為多少?
    1. T=1, p=2
      • Pig1 死, Pig2 活 -> 2有毒
      • Pig1 活, Pig2 死 -> 3有毒
      • Pig1 死, Pig2 死 -> 1有毒
      • Pig1 活, Pig2 活 -> 4有毒
      • 可測試 2^2 個桶子
    o -> 喝爆,  x -> 沒喝
    
    Bucket 1 2 3 4 
    Pig1   o o x x 
    Pig2   o x o x  
    
    1. T=2, p=2
      • Pig1 死, Pig2 活 -> 2,3其中有毒,還有一隻小豬能測試。
      • Pig1 活, Pig2 死 -> 4,5其中有毒,還有一隻小豬能測試。
      • Pig1 死, Pig2 死 -> 1有毒
      • Pig1 活, Pig2 活 -> 6,7,8,9其中有毒,2小豬都活著,使用上面例子即可測試出來。
      • 可測試 3^2 個桶子
    o -> 喝爆,  x -> 沒喝
    
    Bucket 1 2 3 4 5 6 7 8 9
    Pig1   o o o x x x x x x
    Pig2   o x x o o x x x x
    
  5. 從4.1與4.2,我們可以看到能測試最大桶數
    buckets = (T+1)^p
  6. 反推
    p >= log(T+1, buckets)
  7. 阿這裡用C++的log function是以e為底的,即ln。 所以要換底一下。

Code

class Solution {
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int T = minutesToTest/minutesToDie;
        return  static_cast<int>(ceil(log(buckets) / (log(T + 1))));
    }
};

https://ithelp.ithome.com.tw/upload/images/20201007/20129147Z3q6Zd8jbK.png


上一篇
[LeetCode30] Day23 - 37. Sudoku Solver
下一篇
[LeetCode30] Day25 - 483. Smallest Good Base
系列文
LeetCode3030
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言